//Given the root of a binary tree, flatten the tree into a "linked list": 
//
// 
// The "linked list" should use the same TreeNode class where the right child po
//inter points to the next node in the list and the left child pointer is always n
//ull. 
// The "linked list" should be in the same order as a pre-order traversal of the
// binary tree. 
// 
//
// 
// Example 1: 
//
// 
//Input: root = [1,2,5,3,4,null,6]
//Output: [1,null,2,null,3,null,4,null,5,null,6]
// 
//
// Example 2: 
//
// 
//Input: root = []
//Output: []
// 
//
// Example 3: 
//
// 
//Input: root = [0]
//Output: [0]
// 
//
// 
// Constraints: 
//
// 
// The number of nodes in the tree is in the range [0, 2000]. 
// -100 <= Node.val <= 100 
// 
//
// 
//Follow up: Can you flatten the tree in-place (with O(1) extra space)? Related 
//Topics 树 深度优先搜索 
// 👍 820 👎 0


package leetcode.editor.cn;

//Java：Flatten Binary Tree to Linked List
class P114FlattenBinaryTreeToLinkedList {
    public static void main(String[] args) {
        Solution solution = new P114FlattenBinaryTreeToLinkedList().new Solution();
        TreeNode root = new TreeNode(0);
        solution.flatten(root);

        // TO TEST
    }
    //leetcode submit region begin(Prohibit modification and deletion)

    /**
     * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
     *     TreeNode() {}
     *     TreeNode(int val) { this.val = val; }
     *     TreeNode(int val, TreeNode left, TreeNode right) {
     *         this.val = val;
     *         this.left = left;
     *         this.right = right;
     *     }
     * }
     */
    class Solution {
        TreeNode parent = new TreeNode();

        public void flatten1(TreeNode root) {
            if (root == null) {
                return;
            }

            TreeNode left = root.left;
            TreeNode right = root.right;

            parent.right = root;
            parent.left = null;
            parent = root;

            flatten(left);
            flatten(right);
        }

        public void flatten(TreeNode root) {
            TreeNode curr = root;
            while (curr != null) {
                if (curr.left != null) {
                    TreeNode next = curr.left;
                    TreeNode predecessor = next;
                    while (predecessor.right != null) {
                        predecessor = predecessor.right;
                    }
                    predecessor.right = curr.right;
                    curr.left = null;
                    curr.right = next;
                }
                curr = curr.right;
            }
        }

//    public void flatten(TreeNode root) {
//        Queue<TreeNode> queue = new LinkedList<>();
//        preOrder(root, queue);
//        queue.poll();
//        while (!queue.isEmpty()) {
//            root.left = null;
//            root.right = queue.poll();
//            root = root.right;
//        }
//    }
//
//    private void preOrder(TreeNode root, Queue<TreeNode> list) {
//        if (root == null) {
//            return;
//        }
//        list.offer(root);
//        preOrder(root.left, list);
//        preOrder(root.right, list);
//    }
    }
//leetcode submit region end(Prohibit modification and deletion)

}